| 翻訳と辞書 |
| 1-planar graph ： ウィキペディア英語版 |
1-planar graph
In topological graph theory, a 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge.
==Coloring==
1-planar graphs were first studied by , who showed that they can be colored with at most seven colors.〔.〕 Later, the precise number of colors needed to color these graphs, in the worst case, was shown to be six.〔.〕 The example of the complete graph ''K''6, which is 1-planar, shows that 1-planar graphs may sometimes require six colors. However, the proof that six colors are always enough is more complicated.
Ringel's motivation was in trying to solve a variation of total coloring for planar graphs, in which one simultaneously colors the vertices and faces of a planar graph in such a way that no two adjacent vertices have the same color, no two adjacent faces have the same color, and no vertex and face that are adjacent to each other have the same color. This can obviously be done using eight colors by applying the four color theorem to the given graph and its dual graph separately, using two disjoint sets of four colors. However, fewer colors may be obtained by forming an auxiliary graph that has a vertex for each vertex or face of the given planar graph, and in which two auxiliary graph vertices are adjacent whenever they correspond to adjacent features of the given planar graph. A vertex coloring of the auxiliary graph corresponds to a vertex-face coloring of the original planar graph. This auxiliary graph is 1-planar, from which it follows that Ringel's vertex-face coloring problem may also be solved with six colors.〔 The graph ''K''6 cannot be formed as an auxiliary graph in this way, but nevertheless the vertex-face coloring problem also sometimes requires six colors; for instance, if the planar graph to be colored is a triangular prism, then its eleven vertices and faces require six colors, because no three of them may be given a single color.〔.〕
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「1-planar graph」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|